"""
题目：https://leetcode-cn.com/problems/permutations/
    给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

    示例 1：
        输入：nums = [1,2,3]
        输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

方法：回溯法
时间复杂度：O(n*n!),backtrack的调用次数是O(n!),对于backtrack 调用的每个叶结点（共 n!n! 个），我们需要将当前答案使用 O(n) 的时间复制到答案数组中，
          相乘得时间复杂度为 O(n \times n!)O(n×n!)
空间复杂度：O(n)
"""


class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def backtrack(first=0):
            '''
            想生成nums的所有可能的排序序列，我们可以先生成一个序列[x1,x2,x3,x4]，假设fist=1,表明该序列分成两部分，first前是已填充好的数字，
            first后是待填充的数字，具体为：[x1,x2, x3,x4],其中,x1是已填充好的数据，x2,x3,x4表明我们需要从这些数据中选择一个数字填充到first的位置上，填充后，
            序列变为[x1,x4,|,x2,x3],则此时前两个位置的数字已填好，我们需要填充后两个位置的数字。
            '''
            #如果当前待填充的数字位置等于n(即序列长度)的话，将已填充的所有数字放到res中
            if first == n:
                res.append(nums[:])
            #从first位置开始，遍历生成first后的位置可以存放的数字
            for i in range(first,n):
                # 替换 待生成的数字位置first和first后的其他数字
                nums[first],nums[i] = nums[i],nums[first]
                # 生成first+1位置的数字
                backtrack(first + 1)
                # 撤销第i个位置和待生成的数字位置first，此时就完成了回溯操作
                nums[i],nums[first] = nums[first],nums[i]

        n = len(nums)
        res = []
        backtrack()
        return res